package practise;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @ClassName Demo
 * @Description  实现小根堆的基本操作
 * @Author ZJX
 * @Date 2024/7/29 7:45
 * @Version 1.0
 */
public class Demo {
    public static void main(String[] args) {
        int[] arr = { 27,15,19,18,28,34,65,49,25,37 };
        Heap heap = new Heap();
        heap.initElem(arr);
        heap.createHeap();
        heap.add(1);
        heap.poll();


        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(); // 集合类
        priorityQueue.add(1);
        priorityQueue.add(5);
        priorityQueue.add(3);
        priorityQueue.add(9);
        System.out.println(priorityQueue.poll()); //1
        System.out.println(priorityQueue.poll()); // 3
    }

    /*
     * @param arr:
     * @param k:
     * @return int[]
     * @author: ZJX
     * @description:  力扣  最小k个数
     * @date: 2024/7/30 16:50
     */
    public int[] smallestK1(int[] arr, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        for (int i = 0; i < arr.length; i++) {
            priorityQueue.add(arr[i]);
        }

        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }

    /*
     * @param arr:
         * @param k:
      * @return int[]
     * @author: ZJX
     * @description: 优化 Top k 问题
     *      这种方法的核心思想是维护一个大小为k的大根堆，保证堆顶元素是当前最小的k个元素中最大的那个。
     *      这样，当遍历完整个数组后，堆中的元素就是数组中最小的k个元素。
     *      时间复杂度为O(n log k)，其中n是数组的长度。
     * @date: 2024/7/30 23:07
     */
    public int[] smallestK2(int[] arr, int k) {
        // 如果k是0或者数组为空，直接返回空数组
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }

        // 创建一个大小为k的大根堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, Comparator.reverseOrder());

        // 将前k个元素加入堆中
        for (int i = 0; i < k; i++) {
            maxHeap.add(arr[i]);
        }

        // 遍历剩余元素
        for (int i = k; i < arr.length; i++) {
            // 如果当前元素小于堆顶元素，替换堆顶元素
            if (arr[i] < maxHeap.peek()) {
                maxHeap.poll();
//               每次插入或 删除 元素时， PriorityQueue 会自动调整堆，以确保堆的性质
                maxHeap.add(arr[i]);
            }
        }

        // 将堆中的元素放入结果数组中
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = maxHeap.poll();
        }

        return ret;
    }

}
